The present invention relates to data switching, and more particularly to data switching engines of the kind in which a processor array is used to switch data from a plurality of sources to a plurality of destinations in a data communication network.
In recent years, high-speed data communication switching has been accomplished mostly in application specific integrated circuits (ASICs). Programmable logic devices have generally been considered too slow to be relied upon as main switching engines. With recent improvements in programmable logic technology, however, a trend now appears to be emerging toward implementing multiple programmable logic devices in parallel, or parallel processor arrays, as primary data switching engines.
Processor array switching engines provide certain advantages over ASIC switching engines in terms of time-to-market, flexibility and scalability. Still, the xe2x80x9cparallelxe2x80x9d aspect of processor array switching engines creates technical challenges. Foremost among these is how to best allocate the resources of the array. One possibility is to strictly dedicate each processor in the array to a particular group of sources. However, such a dedicated processor array is inefficient since a processor is idle whenever the sources to which it is dedicated are not transmitting packets, even while other processors may be overburdened. A second possibility is to allow each processor in the array to be shared by all sources. Such a shared processor array might greatly increase overall switching efficiency, especially when implemented in conjunction with an efficient load balancing algorithm ensuring that inbound packets are transmitted to the processors presently being underutilized. However, a shared processor array gives rise to other problems, such as how to preserve packet order integrity.
A problem of preserving packet order integrity arises in shared processor arrays because at any given time in the operational cycle of such an array, the time required to process a packet will vary from processor-to-processor. Thus, packets may be switched out of the array in an order different from that in which they were transmitted to the array for switching. While a departure from strict xe2x80x9cfirst in, first outxe2x80x9d sequencing is not a problem for packets applicable to different conversations, it may be for packets applicable to the same conversation.
Accordingly, there is a need for a way to ensure in a processor array in which the processing elements are shared among all sources that packets from the same source leave the array in the sequence in which they arrived. And there is a need for preserving packet ordering for packets from a common source without imposing too high a tax on switching performance.
The present invention provides a method and apparatus for preserving packet order integrity in a shared processor array. The order for packets relating to the same conversation is maintained by checking for each inbound packet whether a previous packet from the same source is pending at a processing element before forwarding the packet to the processor array. If the check reveals that such a packet is pending, the inbound packet is forwarded to the same processing element as the previous packet. If the check reveals that no packet from the same source is pending at any processing element, the inbound packet is forwarded to a processing element in accordance with a load balancing algorithm.